/*
 * @lc app=leetcode.cn id=844 lang=cpp
 *
 * [844] 比较含退格的字符串
 */

// @lc code=start
class Solution
{
public:
    bool backspaceCompare(string s, string t)
    {
        //#代表退格符 这个还是很简单的
        //emm 刚才想的是空间复杂度为On的解法
        //进阶要求是O1
        //如果#之前为空 之后也依然为空
        //不对啊 使用之前的字符串也是On吗 试一下吧
        //还是看了题解 确实双指针 从后往前  比较独特
        //因为#只删除前一个元素 对后面的元素没有影响
        int i = s.size() - 1;
        int j = t.size() - 1;
        int skipi = 0; //代表是否跳过前一个元素
        int skipj = 0;
        while (i >= 0 || j >= 0)
        {
            //对字符串s
            while (i >= 0)
            {
                //分别是三种情况
                //1 skip=0 且 s[i]!='#' 可以比较元素
                //2 s[i]='#' skip++
                //3 s[i]!='#' skip>0 skip--;
                if (s[i] == '#')
                {
                    skipi++;
                    i--;
                }
                else if (skipi)
                {
                    skipi--;
                    i--;
                }
                else
                {
                    break;
                }
            }
            //对字符串t
            while (j >= 0)
            {
                if (t[j] == '#')
                {
                    skipj++;
                    j--;
                }
                else if (skipj)
                {
                    skipj--;
                    j--;
                }
                else
                {
                    break;
                }
            }
            if (i >= 0 && j >= 0)
            {
                //可以比较
                if (s[i] != t[j])
                {
                    return false;
                }
                i--;
                j--;
            }
            else if (i >= 0 || j >= 0)
            {
                //不能比较 有一方或者两方字符串遍历完了
                //此时如果只有一方遍历完了 另一方没有遍历结束 返回false
                return false;
            }
        }
        return true;
    }
};
// @lc code=end
